#ifndef TD_RBTREE_H
#define TD_RBTREE_H

#include<tuple>
#include<concepts>
#include<vector>
#include<QQueue>

template<typename T>
concept Fun=requires(T t,int w,int h,int color,int data){
//        std::same_as<, >
        t(w,h,color,data);
    };

class TD_RBtree
{
public:
    TD_RBtree();
    ~TD_RBtree();
    bool insert(int data_);
    void remove(int data_);
    struct Node;
    void empty();
    template<typename T>
    void visit(Node * & root_,T v);

    template<typename T>
    void print(T t){print(t,fake_root->right_chl);}
    void all_heights(Node * & root_,int cheight);

    template<typename ...T>
    void bfs_visit(T ...v);

public:
    enum class Color{Red,Black};
    struct Node
    {
        int d{};
        Node * left_chl{nullptr};
        Node * right_chl{nullptr};
        Color color{Color::Red};
        int w{0};
        int h{0};
//        Node()
    };

//private:
    Node * fake_root{nullptr};
    Node * null_node{nullptr};
    Node * current_insert{nullptr};
    Node * current_remove{nullptr};
    std::vector<Node *> v{};
private:
    void rotate_with_left(Node * &root_);
    void rotate_with_right(Node * &root_);
    using R_Container=std::tuple<Node* &,Node * &,Node * &>;
    using I_Container=std::tuple<Node* &,Node * &,Node * &,Node * &>;
    bool insert(I_Container c,int data_);
    void rotate_color_fix(I_Container c_);
    bool remove(R_Container c,int data_);
    enum Which{Max,Min};
    template<Which W>
    constexpr Node * find(Node * & root_);

    template<Fun T>
    void print(T t, Node * const & root);
    void sort();
    void empty(Node * & root_);

};

template<typename ...T>
void TD_RBtree::bfs_visit(T ...v)
{
    auto [draw_line,draw_cycle,draw_text]=std::tuple(v...);
    QQueue<Node *> q{};
    q.enqueue(fake_root->right_chl);
    while (q.size()>0) {
        auto c=q.dequeue();
        if(c!=null_node){
            if(c->left_chl!=null_node)
                draw_line(c->w,c->h,c->left_chl->w,c->left_chl->h);
            if(c->right_chl!=null_node)
                draw_line(c->w,c->h,c->right_chl->w,c->right_chl->h);
            draw_cycle(c->w,c->h,c->color==Color::Red?0:1);
            draw_text(c->w,c->h,c->d);
            q.enqueue(c->left_chl);
            q.enqueue(c->right_chl);
        }
    }
}

template<typename T>
void TD_RBtree::visit(TD_RBtree::Node *&root_, T v)
{
    if(root_!=null_node){
        v(root_);
        visit(root_->left_chl,v);
        visit(root_->right_chl,v);
    }
}

template<Fun T>
void TD_RBtree::print(T t, Node * const &root)
{
    if(root!=null_node){
        print(t,root->left_chl);
        t(root->w,root->h,root->color==Color::Red?0:1,root->d);
        print(t,root->right_chl);
    }
}

template<TD_RBtree::Which W>
constexpr TD_RBtree::Node *TD_RBtree::find(Node * & root_)
{
    auto temp=root_;
    if(temp==null_node)
        return temp;
    if constexpr(W==Min){
        while (temp->left_chl!=null_node)
            temp=temp->left_chl;
    }else if constexpr(W==Max){
        while (temp->right_chl!=null_node)
            temp=temp->right_chl;
    }
    return temp;
}

#endif // TD_RBTREE_H
